package leetcode_900;

/**
 *@author 周杨
 *ShortEncodingOfWords_820 相当于给一个段落编码 重复的单词后缀不算做长度
 *describe:用前缀树 AC 42%
 *2018年10月29日 上午10:41:51
 */
public class ShortEncodingOfWords_820 {
	
	 class Node {
	        Node[] next;
	        boolean hasNext;
	        public Node() {
	            next = new Node[26];
	        }
	    }
	    
	    private Node root;
	    
	    private void insert(String s) {
	        Node node = root;
	        for (char c : s.toCharArray()) {
	            if (node.next[c - 'a'] == null) {
	                node.next[c - 'a'] = new Node();
	                node.hasNext = true;
	            }
	            node = node.next[c - 'a'];
	        }
	    }
	    
	    private int find(Node node, int preLen) {
	        if(!node.hasNext) return preLen + 1; // add '#';
	        int res = 0;
	        for (int i = 0; i < 26; i++) {
	            if (node.next[i] != null) res += find(node.next[i], preLen + 1);
	        }
	        return res;
	    }
	    
	    public int minimumLengthEncoding(String[] words) {
	        root = new Node();    
	        for (String w : words) {
	            insert(new StringBuilder(w).reverse().toString());
	        }
	        return find(root, 0);
	    }
	
	/**
	 * describe:题目可能没看太明白 ["me", "time"] 错了
	 * 2018年10月29日 上午10:21:50
	 */
	public int minimumLengthEncoding1(String[] words) {
        int res=words[0].length();
        String before=words[0];
        for(int i=1;i<words.length;++i) {
        	String now=words[i];
        	if(before.endsWith(now))
        		continue;
        	else {
        		before=now;
        		res+=now.length()+1;
        	}
        }
        return res+1;
    }
}
